package sword_offer;

import common.TreeNode;

/**
 * @ClassName _68_1_lowestCommonAncestor
 * @Description: 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/11 12:38
 */
public class _68_1_lowestCommonAncestor {

    // 结合二叉搜索树的性质，对于任何一棵二叉搜索树而言，根大于等于所有左子节点，根小于等于所有右子节点

    // 迭代方式：缩减掉空间的开销
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        // 调整p、q的左右顺序，保证后续比较的大小顺序
        if (p.val > q.val){
            TreeNode temp = p;
            p = q;
            q = temp;
        }
        TreeNode cursor = root;
        while (cursor != null){
            if (p.val <= cursor.val && q.val >= cursor.val){// 这里的顺序有些讲究
                return cursor;
            }else if (cursor.val > p.val){// 由于p q已经保证顺序，所以这里只判断q即可
                cursor = cursor.left;
            }else {
                cursor = cursor.right;
            }
        }
        return cursor;
    }

    public TreeNode lowestCommonAncestorCur(TreeNode root, TreeNode p, TreeNode q){
        if (root == null)
            return null;
        // 调整p、q的左右顺序，保证后续比较的大小顺序
        if (p.val > q.val){
            TreeNode temp = p;
            p = q;
            q = temp;
        }
        return dfs(root, p, q);
    }

    public TreeNode dfs(TreeNode node, TreeNode p, TreeNode q){
        if (node.val >= p.val && node.val <= q.val)
            return node;

        if (node.val > q.val)
            return dfs(node.left, p, q);

        return dfs(node.right, p, q);
    }
}
